package algorithm.swordoff;

import algorithm.leetcode.ListNode;

/**
 * 删除链表的节点
 *
 * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
 * 这题和书上不太一样的地方是书上定义的API是 public ListNode deleteNode(ListNode head, ListNode val)
 * 但是力扣上的API是 public ListNode deleteNode(ListNode head, int val)
 *
 * 第一种情况我自己写的,不确定对不对,思路是按书上写的,但是需要单独处理尾节点情况
 * 返回删除后的链表的头节点
 */

public class SQ18 {
    public ListNode myDeleteNode(ListNode head, ListNode val) {
        ListNode next = val.next;
        if (next != null) {
            val.val = next.val;
            val.next = next.next;
        }

        else  {
            ListNode pre = head;
            while (pre.next != val) pre = pre.next;
            pre.next = null;
        }
        return head;
    }

    public ListNode deleteNode(ListNode head, int val) {
        ListNode fakeHead = new ListNode(-21412783);
        ListNode prev = fakeHead;
        prev.next = head;
        ListNode curr = head;

        while (curr != null) {

            if (curr.val == val) {
                ListNode next = curr.next;
                curr.next = null;
                prev.next = next;
                break;
            }

            // 若无事发生,则指针后移
            prev = curr;
            curr = curr.next;

        }

        return fakeHead.next;
    }

    /**
     * 删除链表中全部节点值等于val的节点
     * @param head
     * @param val
     * @return
     */
    public ListNode deleteNode2(ListNode head, int val) {
        ListNode fakeHead = new ListNode(-1213);
        fakeHead.next = head;
        ListNode prev = fakeHead;
        ListNode curr = head;

        while (curr != null) {

            if (curr.val == val) {
                prev.next = curr.next;
                curr.next = null;
                curr = prev.next;
            }

            prev = curr;
            if (curr != null) curr = curr.next;
        }

        return fakeHead.next;
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        ListNode f = new ListNode(2);
//        ListNode f = new ListNode(6);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = f;
//        e.next = f;
        SQ18 soe = new SQ18();
        // System.out.println(soe.myDeleteNode(a, b));
        System.out.println(soe.deleteNode(a, b.val));
        System.out.println(soe.deleteNode2(a, b.val));

    }
}
